Medium
Related Topics: Hash Table / Math / Dynamic Programming / Heap (Priority Queue)
LeetCode Source

解題想法

首先初始化一個 vector res，並定義 res[0] = 1，因為 1 是第一個 ugly number

接著我們透過 3 個 pointer count_2、count_3、count_5 來了解 ugly 出現的時機

res[i] = min(res[count_2]*2, res[count_3]*3);
res[i] = min(res[i], res[count_5]*5);

res[i] 都是儲存最小的 ugly number

接下來就是解決 duplicate ugly number 的時候

我們透過 3 個獨立的條件式判斷

如果有符合，則該 pointer 會加一

最後 res[n-1] 就是第n個 ugly number

Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Python

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        res = [0] * n
        count_2, count_3, count_5 = 0, 0, 0
        res[0] = 1

        for i in range(1, n):
            res[i] = min(res[count_2]*2, res[count_3]*3, res[count_5]*5)
            if res[i] == res[count_2]*2:
                count_2 += 1
            if res[i] == res[count_3]*3:
                count_3 += 1
            if res[i] == res[count_5]*5:
                count_5 += 1
        return res[n-1]

C++

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> res (n, 0);
        res[0] = 1;
        int count_2 = 0, count_3 = 0, count_5 = 0;

        for (int i = 1; i < n; i++) {
            res[i] = min(res[count_2]*2, res[count_3]*3);
            res[i] = min(res[i], res[count_5]*5);

            if (res[i] == res[count_2] * 2)
                count_2 += 1;
            if (res[i] == res[count_3] * 3)
                count_3 += 1;
            if (res[i] == res[count_5] * 5)
                count_5 += 1;
        }
        return res[n-1];
    }
};